/**
 * 描述：小兵向前冲
 *
 * @author wangb
 * @version 1.0
 * create 2018-11-04-23:18
 */
public class LittleSoldier{
    public static final int N = 10;
    public static final int M = 10;

    //改动了一下。。。。

    public static int[][] result;

    /**
     * 记忆化搜索
     * @param n
     * @param m
     * @return
     */
    public static int solve(int n ,int m ){
        if(n == 0 || m == 0)
            return 1;


        if(result[n][m] >= 0)
            return result[n][m];

        result[n][m] = solve (n -1,m) + solve (n ,m -1);
        return result[n][m];


    }

    public static int solveDitui(int n ,int m){
        for ( int i = 0 ; i <= N  ; i++ ) {
            result[i][0] = 1;
        }
        for ( int i = 0 ; i <=M  ; i++ ) {
            result[0][i] = 1;
        }

        for ( int i = 1 ; i <=N  ; i++ ) {
            for ( int j = 1 ; j <=M  ; j++ ) {
                result[i][j] = result[i-1][j] + result[i][j-1];
            }
        }
        return result[n][m];
    }


    public static void main(String[] args){
        result = new int[N + 1][M + 1];
        for ( int i = 0 ; i <=N; i++ ) {
            for ( int j = 0 ; j <=M  ; j++ ) {
                result[i][j] = -1;
            }
        }

        int s = solve (N,M);
        System.out.println ("递归的结果：");
        System.out.println (s);
        s = solveDitui (N,M);
        System.out.println ("递推的结果：");
        System.out.println (s);
    }
}
